class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s
        next = [-1] * (len(s))
        k= -1
        j=0
        while j< len(next) - 1:
            if k==-1 or s[j] == s[k]:
                k = k+1
                j = j +1
                if s[j] == s[k]:
                    next[j] = next[k]
                else:
                    next[j] = k
            else:
                k = next[k]
        return next
        # hadEnd = len(s) - 1
        #
        # start = 0
        # end = hadEnd
        # had = True
        # while start <= end:
        #     if s[start] == s[end]:
        #         start = start + 1
        #         end = end - 1
        #     else:
        #         if next[start] == -1:
        #             start = 0
        #             end = end - 1
        #             hadEnd = end
        #         else:
        #             start = next[start]
        #             hadEnd = end + start
        # if not had:
        #     hadEnd = hadEnd - 1
        #
        # newS = list(s[hadEnd + 1:])
        # newS.reverse()
        # return ''.join(newS) + s


# KMP算法
if __name__ == '__main__':
    so = Solution()
    s = "aacecaaac"
    r = so.shortestPalindrome(s)
    print(r)
